Докладчик

Цель работы

Ознакомиться с pho-методом Полларда. Реализовать его.

Задачи

1. Реализовать на языке программирования Julia pho-метод Полларда.
2. Разложить на множители число 1359331.

Разложение на множители

pho-метод Полларда (или \(\rho-1\) метод Полларда) является одним из алгоритмов для факторизации целых чисел, который особенно эффективен для нахождения малых простых делителей. Он основан на свойствах чисел и использует последовательности, чтобы вычислить делители.

Основные этапы метода

1. Подготовка:
   • Выбор числа n: Начинаем с целого числа n, которое необходимо факторизовать;
   • Выбор параметров: Выбираем небольшое целое число a и границу B, которая будет использоваться для ограничения множителей.
2. Генерация последовательности: Создаем последовательность чисел по формуле: \(x_{k+1} = (x_k^2 + a)\).
3. Вычисление НОД: На каждом шаге вычисляем наибольший общий делитель (НОД) между n и разностью двух членов последовательности.
4. Проверка результата: Если найденный НОД d больше 1 и меньше n, то это делитель числа n. Если \(d = n\), то алгоритм не дал результата, и его можно повторить с другими параметрами. Если \(d=1\), то повторяем действия со второго шага.
5. Завершение: Процесс продолжается до тех пор, пока не будет найден делитель или не исчерпаются все возможные варианты.

pho-метод Полларда

function pollard(n, c, f::Function)
    # step 1
    a = c
    b = c
    # step 2-4
    println(a, "\t", b, "\t")
    while true
        # step 2
        a = f(a) % n
        b = f(b) % n
        b = f(b) % n 

pho-метод Полларда

        # step 3
        d = binary_gcd(abs(a-b),n)
        
        println(a, "\t", b, "\t", d)
        # step 4
        if 1 < d < n
            return d, round(Int, n/d)
        elseif d == n
            return "Delitel ne naiden"
        end
    end
end

pho-метод Полларда. Результат работы программного кода

Рисунок 1: pho-метод Полларда. Пример

Вывод

В ходе лабораторной работы был изучен pho-метод Полларда.